Traditional Structured Query Language (SQL) data types have all fallen into the categories of numeric data types, character data types, binary data types, and date and time interval types. All of these initial SQL data type offerings were scalar data types that fit nicely into an extendible-hashing based file system environment, in which a hash-function was executed against the data value corresponding to a particular data type and the result of the hash function was then utilized to determine where the data was to be stored within the file system. Later, when a particular data value was being searched for, the same hash-function could be applied to that value and the result used to find the matching data (if any) within the file system. Another subject area in which this scalar-data-type hashing scheme seemed well fitted, was with regards to efficiently resolving queries involving the relational operators: >,<,=, etc.
Most modern commercial databases provide the user with an ability to index any one of their scalar data type columns. The indexing scheme typically employs the same storage/retrieval mechanism that is available for the storage of the data itself. Thus to retrieve the row or rows associated with a particular index search-value, the search-value is first hashed, and the hashed-value is then used to retrieve the row or rows from the database that fulfill the search condition.
Recently, however, spatial data types were introduced into the ANSI SQL standard. Spatial data types are not scalar and in fact represent for the most part multi-dimensional shapes: Circles, Squares, Rectangles, Polygons, etc. Unlike scalar SQL data types, spatial data types have a large number of SQL operators that can be applied against them: touches, intersects, overlaps, within, disjoint, crosses, distance, etc.; all of which must be executed in an efficient manner. The dilemma is that spatial data types do not fit in well with either an extendible-hash based file system or an extendible-hash based indexing mechanism. Although there has been research that has investigated mapping multi-dimensional objects, represented by multi-dimensional coordinates, into a linear value, a major shortfall with this approach is that there is no way to perform the linear mapping and a the same time maintain the spatial relationships between mapped objects in order to efficiently execute the aforementioned spatial operations.
In other words, one can perform the mapping, but then one will find a difficult time in executing such operations as crosses, touches, etc., in an efficient manner. To perform these operations in an efficient manner, one would need a specialized spatial construct such as an R-Tree-based index. This index provides a mechanism by which spatial objects are stored/retrieved while simultaneously maintaining inter-spatial object relationships. An R-Tree approach is built around the concept of a Minimum Bounding Rectangle (MBR). The MBR is used to decide where data is to be stored within the file system/index containing the spatial data.
However, conventional approaches that attempt to provide R-Tree indexes require the R-Tree to be built and constructed out of physical disk blocks. So, that changes to existing conventional indexes to accommodate an R-Tree becomes essentially impractical to achieve and risky to existing database file systems.